package ua.yandex.collections;

import java.util.Comparator;

public class MyCollections {

    // Reverses the order of the elements in the specified list
    public static void reverse(MyList list) {
        Object[] objectList = list.toArray();
        for (int i = 0; i < objectList.length; i++) {
            list.set(i, objectList[objectList.length - 1 - i]);
        }
    }

    //Реализует рекурсивный поиск в отсортированном массиве методом бисекции.
    public static int binarySearch(MyList list, Object key) {
        int lowerBound = 0;
        int upperBound = list.size() - 1;
        while (lowerBound <= upperBound) {
            if (lowerBound == upperBound) {
                if (list.get(upperBound).equals(key)) {
                    return upperBound;
                } else {
                    return -1 - lowerBound;
                }
            } else {
                int middle = (lowerBound + upperBound) / 2;
                if (((Integer) key <= (Integer) list.get(middle))
                        && ((Integer) list.get(lowerBound)
                        <= (Integer) list.get(upperBound))
                        || (((Integer) key >= (Integer) list.get(middle))
                        && ((Integer) list.get(lowerBound)
                        >= (Integer) list.get(upperBound)))) {
                    upperBound = middle;
                } else {
                    lowerBound = middle + 1;
                }
            }
        }
        return -1;
    }

    //Реализует рекурсивный поиск в отсортированном массиве методом бисекции.
    public static int binarySearch(MyList list, Object key, Comparator cp) {
        int lowerBound = 0;
        int upperBound = list.size() - 1;
        while (lowerBound <= upperBound) {
            if (lowerBound == upperBound) {
                if (list.get(upperBound).equals(key)) {
                    return upperBound;
                } else {
                    return -1 - lowerBound;
                }
            } else {
                int middle = (lowerBound + upperBound) / 2;
                int keysCmp = cp.compare((Comparable) key,
                        (Comparable) list.get(middle));
                int boundCmp = cp.compare((Comparable) list.get(lowerBound),
                        (Comparable) list.get(upperBound));
                if (((keysCmp <= 0) && (boundCmp <= 0))
                        || ((keysCmp >= 0) && (boundCmp >= 0))) {
                    upperBound = middle;
                } else {
                    lowerBound = middle + 1;
                }
            }
        }

        return -1;
    }
}
